function RandomListNode(x){
  this.label = x;
  this.next = null;
  this.random = null;
}
function Clone(pHead)
{
  // write code here
  // 首先处理特殊的情况 
  if(pHead === null) return null
  // 1.复制节点的值val 并且放到原节点后面
  // 从头结点开始,只要不为null 就构造一个cur的副本 curCopy
  var cur = pHead // 从头结点开始
  while(cur) { // 只要cur不是null 就复制一个副本
    var curCopy = new RandomListNode(cur.label) // 节点值是原节点的值
    // 接下来我们要把它给插入到原来节点的后面
    // 先让这个副本的next指针指向原节点的next
    curCopy.next = cur.next
    // 接着修改原节点的next属性 为 这个复制后的这个副本 
    cur.next = curCopy
    // 我们这个cur移动到原来链表当中的后续的节点
    cur = curCopy.next
    // 这样就完成了第一步
  }
  // 2.构造random 
  // 我们依然是从头节点开始
  cur = pHead // 依然从头结点开始
  while(cur){
    // 如果说当前节点的随机指针不为null 那么我们就让它的拷贝的节点的随机指针指向的是当前节点的随机指针的后续的一个节点
    if(cur.random){
      cur.next.random = cur.random.next
    }
    // 并且我们让cur往后面移动两个节点
    cur = cur.next.next // 因为cur的后面是它的一个拷贝 我们就不用管它 因为我们只想遍历的是 原复杂链表当中的所有节点
  }
  // 3.拆分我们的链表 
  // 依然是从头结点开始
  cur = pHead
  var newHead = pHead.next // 我们用一个newHead用来记录一下最终要返回的头结点
  while(cur.next){ // 只要是cur的next指针不为null
    // 要修改的next的指针的所有节点是倒数第二个节点为止,因为倒数第一个节点它指向的后一个节点就是null了没有必要再去管它了
    var temp = cur.next // 我们先用一个temp来存储他的next节点
    cur.next = temp.next // 间隔一个节点相连
    // 在这之后我们再让cur指向temp
    cur = temp // 如此直到最后一个倒数第二个节点之后呢 我们把倒数第一个节点的next 也就把一个空的倒数第二个节点赋给了倒数第一个节点
  }
  return newHead // 最后返回新的头结点
}
module.exports = {
  Clone : Clone
};